SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Implicit graph</title>

</head>

Implicit graph

</h1>

</header>

In the study of <a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">graph algorithms</a>, an implicit graph representation (or more simply implicit graph) is a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> whose <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> or edges are not represented as explicit objects in a computer's memory, but rather are determined <a href="Algorithm" title="Algorithm">algorithmically</a> from some other input, for example a <a href="Computable_function" title="Computable function">computable function</a>.

<div class="mw-heading mw-heading2"><h2 id="Neighborhood_representations">Neighborhood representations</h2></div>

The notion of an implicit graph is common in various <a href="Search_algorithm" title="Search algorithm">search algorithms</a> which are described in terms of graphs. In this context, an implicit graph may be defined as a set of rules to define all <a href="Neighborhood_(graph_theory)" class="mw-redirect" title="Neighborhood (graph theory)">neighbors</a> for any specified vertex.<a href="#cite_note-1">[1]</a> This type of implicit graph representation is analogous to an <a href="Adjacency_list" title="Adjacency list">adjacency list</a>, in that it provides easy access to the neighbors of each vertex. For instance, in searching for a solution to a puzzle such as <a href="Rubik's_Cube" title="Rubik's Cube">Rubik's Cube</a>, one may define an implicit graph in which each vertex represents one of the possible states of the cube, and each edge represents a move from one state to another. It is straightforward to generate the neighbors of any vertex by trying all possible moves in the puzzle and determining the states reached by each of these moves; however, an implicit representation is necessary, as the state space of Rubik's Cube is too large to allow an algorithm to list all of its states.<a href="#cite_note-2">[2]</a>

In <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, several <a href="Complexity_class" title="Complexity class">complexity classes</a> have been defined in connection with implicit graphs, defined as above by a rule or algorithm for listing the neighbors of a vertex. For instance, <a href="PPA_(complexity)" title="PPA (complexity)">PPA</a> is the class of problems in which one is given as input an undirected implicit graph (in which vertices are n-bit binary strings, with a <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> algorithm for listing the neighbors of any vertex) and a vertex of odd degree in the graph, and must find a second vertex of odd degree. By the <a href="Handshaking_lemma" title="Handshaking lemma">handshaking lemma</a>, such a vertex exists; finding one is a problem in <a href="NP_(complexity)" title="NP (complexity)">NP</a>, but the problems that can be defined in this way may not necessarily be <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>, as it is unknown whether PPA = NP. <a href="PPAD_(complexity)" title="PPAD (complexity)">PPAD</a> is an analogous class defined on implicit <a href="Directed_graph" title="Directed graph">directed graphs</a> that has attracted attention in <a href="Algorithmic_game_theory" title="Algorithmic game theory">algorithmic game theory</a> because it contains the problem of computing a <a href="Nash_equilibrium" title="Nash equilibrium">Nash equilibrium</a>.<a href="#cite_note-3">[3]</a> The problem of testing <a href="Reachability" title="Reachability">reachability</a> of one vertex to another in an implicit graph may also be used to characterize space-bounded nondeterministic complexity classes including <a href="NL_(complexity)" title="NL (complexity)">NL</a> (the class of problems that may be characterized by reachability in implicit directed graphs whose vertices are O(log n)-bit bitstrings), <a href="SL_(complexity)" title="SL (complexity)">SL</a> (the analogous class for undirected graphs), and <a href="PSPACE" title="PSPACE">PSPACE</a> (the class of problems that may be characterized by reachability in implicit graphs with polynomial-length bitstrings). In this complexity-theoretic context, the vertices of an implicit graph may represent the states of a <a href="Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">nondeterministic Turing machine</a>, and the edges may represent possible state transitions, but implicit graphs may also be used to represent many other types of combinatorial structure.<a href="#cite_note-4">[4]</a> <a href="PLS_(complexity)" title="PLS (complexity)">PLS</a>, another complexity class, captures the complexity of finding local optima in an implicit graph.<a href="#cite_note-5">[5]</a>

Implicit graph models have also been used as a form of <a href="Relativization" class="mw-redirect" title="Relativization">relativization</a> in order to prove separations between complexity classes that are stronger than the known separations for non-relativized models. For instance, Childs et al. used neighborhood representations of implicit graphs to define a graph traversal problem that can be solved in polynomial time on a <a href="Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computer</a> but that requires exponential time to solve on any classical computer.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Adjacency_labeling_schemes">Adjacency labeling schemes</h2></div>

In the context of efficient representations of graphs, J. H. Muller defined a local structure or adjacency labeling scheme for a graph G in a given family F of graphs to be an assignment of an O(log n)-bit identifier to each vertex of G, together with an algorithm (that may depend on F but is independent of the individual graph G) that takes as input two vertex identifiers and determines whether or not they are the endpoints of an edge in G. That is, this type of implicit representation is analogous to an <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a>: it is straightforward to check whether two vertices are adjacent but finding the neighbors of any vertex may involve looping through all vertices and testing which ones are neighbors.<a href="#cite_note-muller-7">[7]</a>

Graph families with adjacency labeling schemes include:

<dl><dt>Bounded degree graphs</dt>

<dd>If every vertex in G has at most d neighbors, one may number the vertices of G from 1 to n and let the identifier for a vertex be the (d + 1)-tuple of its own number and the numbers of its neighbors. Two vertices are adjacent when the first numbers in their identifiers appear later in the other vertex's identifier. More generally, the same approach can be used to provide an implicit representation for graphs with bounded <a href="Arboricity" title="Arboricity">arboricity</a> or bounded <a href="Degeneracy_(graph_theory)" title="Degeneracy (graph theory)">degeneracy</a>, including the <a href="Planar_graph" title="Planar graph">planar graphs</a> and the graphs in any <a href="Robertson%E2%80%93Seymour_theorem" title="Robertson–Seymour theorem">minor-closed graph family</a>.<a href="#cite_note-knr-8">[8]</a><a href="#cite_note-9">[9]</a></dd>

<dt>Intersection graphs</dt>

<dd>An <a href="Interval_graph" title="Interval graph">interval graph</a> is the <a href="Intersection_graph" title="Intersection graph">intersection graph</a> of a set of <a href="Line_segment" title="Line segment">line segments</a> in the <a href="Real_line" class="mw-redirect" title="Real line">real line</a>. It may be given an adjacency labeling scheme in which the points that are endpoints of line segments are numbered from 1 to 2n and each vertex of the graph is represented by the numbers of the two endpoints of its corresponding interval. With this representation, one may check whether two vertices are adjacent by comparing the numbers that represent them and verifying that these numbers define overlapping intervals. The same approach works for other geometric intersection graphs including the graphs of bounded <a href="Boxicity" title="Boxicity">boxicity</a> and the <a href="Circle_graph" title="Circle graph">circle graphs</a>, and subfamilies of these families such as the <a href="Distance-hereditary_graph" title="Distance-hereditary graph">distance-hereditary graphs</a> and <a href="Cograph" title="Cograph">cographs</a>.<a href="#cite_note-knr-8">[8]</a><a href="#cite_note-spinrad-10">[10]</a> However, a geometric intersection graph representation does not always imply the existence of an adjacency labeling scheme, because it may require more than a logarithmic number of bits to specify each geometric object. For instance, representing a graph as a <a href="Unit_disk_graph" title="Unit disk graph">unit disk graph</a> may require exponentially many bits for the coordinates of the disk centers.<a href="#cite_note-11">[11]</a></dd>

<dt>Low-dimensional comparability graphs</dt>

<dd>The <a href="Comparability_graph" title="Comparability graph">comparability graph</a> for a <a href="Partially_ordered_set" title="Partially ordered set">partially ordered set</a> has a vertex for each set element and an edge between two set elements that are related by the partial order. The <a href="Order_dimension" title="Order dimension">order dimension</a> of a partial order is the minimum number of linear orders whose intersection is the given partial order. If a partial order has bounded order dimension, then an adjacency labeling scheme for the vertices in its comparability graph may be defined by labeling each vertex with its position in each of the defining linear orders, and determining that two vertices are adjacent if each corresponding pair of numbers in their labels has the same order relation as each other pair. In particular, this allows for an adjacency labeling scheme for the <a href="Chordal_graph" title="Chordal graph">chordal</a> <a href="Comparability_graph" title="Comparability graph">comparability graphs</a>, which come from partial orders of dimension at most four.<a href="#cite_note-12">[12]</a><a href="#cite_note-13">[13]</a></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="The_implicit_graph_conjecture">The implicit graph conjecture</h3></div>

Not all graph families have local structures. For some families, a simple counting argument proves that adjacency labeling schemes do not exist: only O(n log n) bits may be used to represent an entire graph, so a representation of this type can only exist when the number of n-vertex graphs in the given family F is at most 2O(n log n). Graph families that have larger numbers of graphs than this, such as the <a href="Bipartite_graph" title="Bipartite graph">bipartite graphs</a> or the <a href="Triangle-free_graph" title="Triangle-free graph">triangle-free graphs</a>, do not have adjacency labeling schemes.<a href="#cite_note-knr-8">[8]</a><a href="#cite_note-spinrad-10">[10]</a> However, even families of graphs in which the number of graphs in the family is small might not have an adjacency labeling scheme; for instance, the family of graphs with fewer edges than vertices has 2O(n log n) n-vertex graphs but does not have an adjacency labeling scheme, because one could transform any given graph into a larger graph in this family by adding a new isolated vertex for each edge, without changing its labelability.<a href="#cite_note-muller-7">[7]</a><a href="#cite_note-spinrad-10">[10]</a> Kannan et al. asked whether having a <a href="Forbidden_graph_characterization" title="Forbidden graph characterization">forbidden subgraph characterization</a> and having at most 2O(n log n) n-vertex graphs are together enough to guarantee the existence of an adjacency labeling scheme; this question, which Spinrad restated as a conjecture. Recent work has refuted this conjecture by providing a family of graphs with a forbidden subgraph characterization and a slow-enough growth rate but with no adjacency labeling scheme.<a href="#cite_note-14">[14]</a>

Among the families of graphs which satisfy the conditions of the conjecture and for which there is no known adjacency labeling scheme are the family of disk graphs and line segment intersection graphs.

<div class="mw-heading mw-heading3"><h3 id="Labeling_schemes_and_induced_universal_graphs">Labeling schemes and induced universal graphs</h3></div>

If a graph family F has an adjacency labeling scheme, then the n-vertex graphs in F may be represented as <a href="Induced_subgraph" title="Induced subgraph">induced subgraphs</a> of a common induced <a href="Universal_graph" title="Universal graph">universal graph</a> of polynomial size, the graph consisting of all possible vertex identifiers. Conversely, if an induced universal graph of this type can be constructed, then the identities of its vertices may be used as labels in an adjacency labeling scheme.<a href="#cite_note-knr-8">[8]</a> For this application of implicit graph representations, it is important that the labels use as few bits as possible, because the number of bits in the labels translates directly into the number of vertices in the induced universal graph. Alstrup and Rauhe showed that any tree has an adjacency labeling scheme with log2 n + O(<a href="Iterated_logarithm" title="Iterated logarithm">log*</a> n) bits per label, from which it follows that any graph with <a href="Arboricity" title="Arboricity">arboricity</a> k has a scheme with k log2 n + O(<a href="Iterated_logarithm" title="Iterated logarithm">log*</a> n) bits per label and a universal graph with nk2O(<a href="Iterated_logarithm" title="Iterated logarithm">log*</a> n) vertices. In particular, planar graphs have arboricity at most three, so they have universal graphs with a nearly-cubic number of vertices.<a href="#cite_note-15">[15]</a>

This bound was improved by Gavoille and Labourel who showed that planar graphs and minor-closed graph families have a labeling scheme with 2 log2 n + O(log log n) bits per label, and that graphs of bounded <a href="Treewidth" title="Treewidth">treewidth</a> have a labeling scheme with log2 n + O(log log n) bits per label.<a href="#cite_note-16">[16]</a>

The bound for planar graphs was improved again by Bonamy, Gavoille, and Piliczuk who showed that planar graphs have a labelling scheme with (4/3+o(1))log2 n bits per label.<a href="#cite_note-17">[17]</a>

Finally Dujmović et al showed that planar graphs have a labelling scheme with (1+o(1))log2 n bits per label giving a universal graph with n1+o(1) vertices.<a href="#cite_note-18">[18]</a>

<div class="mw-heading mw-heading2"><h2 id="Evasiveness">Evasiveness</h2></div>

The <a href="Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" title="Aanderaa–Karp–Rosenberg conjecture">Aanderaa–Karp–Rosenberg conjecture</a> concerns implicit graphs given as a set of labeled vertices with a black-box rule for determining whether any two vertices are adjacent. This definition differs from an adjacency labeling scheme in that the rule may be specific to a particular graph rather than being a generic rule that applies to all graphs in a family. Because of this difference, every graph has an implicit representation. For instance, the rule could be to look up the pair of vertices in a separate adjacency matrix. However, an algorithm that is given as input an implicit graph of this type must operate on it only through the implicit adjacency test, without reference to how the test is implemented.

A graph property is the question of whether a graph belongs to a given family of graphs; the answer must remain invariant under any relabeling of the vertices. In this context, the question to be determined is how many pairs of vertices must be tested for adjacency, in the worst case, before the property of interest can be determined to be true or false for a given implicit graph. Rivest and Vuillemin proved that any deterministic algorithm for any nontrivial graph property must test a quadratic number of pairs of vertices.<a href="#cite_note-19">[19]</a> The full Aanderaa–Karp–Rosenberg conjecture is that any deterministic algorithm for a monotonic graph property (one that remains true if more edges are added to a graph with the property) must in some cases test every possible pair of vertices. Several cases of the conjecture have been proven to be true—for instance, it is known to be true for graphs with a prime number of vertices<a href="#cite_note-20">[20]</a>—but the full conjecture remains open. Variants of the problem for randomized algorithms and quantum algorithms have also been studied.

Bender and Ron have shown that, in the same model used for the evasiveness conjecture, it is possible in only constant time to distinguish <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graphs</a> from graphs that are very far from being acyclic. In contrast, such a fast time is not possible in neighborhood-based implicit graph models,<a href="#cite_note-21">[21]</a>

<ul><li><a href="Black_box_group" title="Black box group">Black box group</a>, an implicit model for <a href="Group_theory" title="Group theory">group-theoretic</a> algorithms</li>

<li><a href="Matroid_oracle" title="Matroid oracle">Matroid oracle</a>, an implicit model for <a href="Matroid" title="Matroid">matroid</a> algorithms</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKorf2008" class="citation cs2"><a href="Richard_E._Korf" title="Richard E. Korf">Korf, Richard E.</a> (2008), "Linear-time disk-based implicit graph search", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 55 (6) 26: 1–40, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1455248.1455250">10.1145/1455248.1455250</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2477486">2477486</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13969607">13969607</a></cite>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKorf2008" class="citation cs2"><a href="Richard_E._Korf" title="Richard E. Korf">Korf, Richard E.</a> (2008), <a rel="nofollow" class="external text" href="http://www.aaai.org/Papers/AAAI/2008/AAAI08-050.pdf">"Minimizing disk I/O in two-bit breadth-first search"</a> (PDF), Proc. 23rd AAAI Conf. on Artificial Intelligence, pp. 317–324, <q>The standard 3×3×3 Rubik's Cube contains 4.3252 × 1019 states, and is too large to search exhaustively.</q></cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFPapadimitriou1994" class="citation cs2"><a href="Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, Christos</a> (1994), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf">"On the complexity of the parity argument and other inefficient proofs of existence"</a> (PDF), <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>, 48 (3): 498–532, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2805%2980063-7">10.1016/S0022-0000(05)80063-7</a>, archived from <a rel="nofollow" class="external text" href="http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf">the original</a> (PDF) on 2016-03-04, retrieved 2011-07-12</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFImmerman1999" class="citation cs2"><a href="Neil_Immerman" title="Neil Immerman">Immerman, Neil</a> (1999), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=kWSZ0OWnupkC&pg=PA48">"Exercise 3.7 (Everything is a Graph)"</a>, <a href="Descriptive_Complexity" title="Descriptive Complexity">Descriptive Complexity</a>, Graduate Texts in Computer Science, Springer-Verlag, p. 48, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-98600-5</bdi></cite>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFYannakakis2009" class="citation cs2"><a href="Mihalis_Yannakakis" title="Mihalis Yannakakis">Yannakakis, Mihalis</a> (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0802.2831">0802.2831</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.cosrev.2009.03.004">10.1016/j.cosrev.2009.03.004</a></cite>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFChildsCleveDeottoFarhi2003" class="citation cs2">Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Exponential algorithmic speedup by a quantum walk", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing</a>, New York: ACM, pp. 59–68, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0209131">quant-ph/0209131</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F780542.780552">10.1145/780542.780552</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58113-674-9</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2121062">2121062</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:308884">308884</a></cite>.

</li>

<li id="cite_note-muller-7">^ <a href="#cite_ref-muller_7-0">a</a> <a href="#cite_ref-muller_7-1">b</a> <cite id="CITEREFMuller1988" class="citation cs2">Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology</cite>.

</li>

<li id="cite_note-knr-8">^ <a href="#cite_ref-knr_8-0">a</a> <a href="#cite_ref-knr_8-1">b</a> <a href="#cite_ref-knr_8-2">c</a> <a href="#cite_ref-knr_8-3">d</a> <cite id="CITEREFKannanNaorRudich1992" class="citation cs2">Kannan, Sampath; <a href="Moni_Naor" title="Moni Naor">Naor, Moni</a>; <a href="Steven_Rudich" title="Steven Rudich">Rudich, Steven</a> (1992), "Implicit representation of graphs", <a href="SIAM_Journal_on_Discrete_Mathematics" title="SIAM Journal on Discrete Mathematics">SIAM Journal on Discrete Mathematics</a>, 5 (4): 596–603, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0405049">10.1137/0405049</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1186827">1186827</a></cite>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFChrobakEppstein1991" class="citation cs2">Chrobak, Marek; <a href="David_Eppstein" title="David Eppstein">Eppstein, David</a> (1991), <a rel="nofollow" class="external text" href="http://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf">"Planar orientations with low out-degree and compaction of adjacency matrices"</a> (PDF), <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 86 (2): 243–266, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2891%2990020-3">10.1016/0304-3975(91)90020-3</a></cite>.

</li>

<li id="cite_note-spinrad-10">^ <a href="#cite_ref-spinrad_10-0">a</a> <a href="#cite_ref-spinrad_10-1">b</a> <a href="#cite_ref-spinrad_10-2">c</a> <cite id="CITEREFSpinrad2003" class="citation cs2">Spinrad, Jeremy P. (2003), "2. Implicit graph representation", <a rel="nofollow" class="external text" href="https://books.google.com/books?id=RrtXSKMAmWgC&pg=PA17">Efficient Graph Representations</a>, American Mathematical Soc., pp. 17–30, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8218-2815-0</bdi></cite>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFKangMüller2011" class="citation cs2">Kang, Ross J.; Müller, Tobias (2011), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120316103530/http://homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf">Sphere and dot product representations of graphs</a> (PDF), archived from <a rel="nofollow" class="external text" href="http://homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf">the original</a> (PDF) on 2012-03-16, retrieved 2011-07-12</cite>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFMaSpinrad1991" class="citation cs2">Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Cycle-free partial orders and chordal comparability graphs", <a href="Order_(journal)" title="Order (journal)">Order</a>, 8 (1): 49–61, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00385814">10.1007/BF00385814</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1129614">1129614</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:120479154">120479154</a></cite>.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFCurtisIzurietaJoerisLundberg2010" class="citation cs2">Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "An implicit representation of chordal comparability graphs in linear time", Discrete Applied Mathematics, 158 (8): 869–875, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2010.01.005">10.1016/j.dam.2010.01.005</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2602811">2602811</a></cite>.

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFHatamiHatami2022" class="citation cs2">Hatami, Hamed; Hatami, Pooya (2022), "The implicit graph conjecture is false", 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 – November 3, 2022, IEEE, pp. 1134–1137, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2111.13198">2111.13198</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS54457.2022.00109">10.1109/FOCS54457.2022.00109</a></cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFAlstrupRauhe2002" class="citation cs2">Alstrup, Stephen; Rauhe, Theis (2002), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110927094246/http://www.it-c.dk/research/algorithms/Kurser/AD/2002E/Uge7/parent.pdf">"Small induced-universal graphs and compact implicit graph representations"</a> (PDF), <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science</a>, pp. 53–62, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.2002.1181882">10.1109/SFCS.2002.1181882</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-1822-2</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1820524">1820524</a>, archived from <a rel="nofollow" class="external text" href="http://www.it-c.dk/research/algorithms/Kurser/AD/2002E/Uge7/parent.pdf">the original</a> (PDF) on 2011-09-27, retrieved 2011-07-13</cite>.

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFArnaudGavoille2007" class="citation cs2">Arnaud, Labourel; Gavoille, Cyril (2007), <a rel="nofollow" class="external text" href="http://dept-info.labri.fr/~gavoille/article/GL07.pdf">"Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs"</a> (PDF), <a href="European_Symposium_on_Algorithms" title="European Symposium on Algorithms">Proceedings of the 15th annual European Symposium on Algorithms</a>, Lecture Notes in Computer Science, vol. 4698, pp. 582–593, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-75520-3_52">10.1007/978-3-540-75520-3_52</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-75519-7</bdi></cite>.

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFBonamyGavoillePilipczuk2020" class="citation cs2">Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Shorter Labeling Schemes for Planar Graphs", <a href="Symposium_on_Discrete_Algorithms" title="Symposium on Discrete Algorithms">Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms</a>, pp. 446–462, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1908.03341">1908.03341</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-75520-3_52">10.1007/978-3-540-75520-3_52</a></cite>.

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFDujmovićEsperetJoretGavoille2020" class="citation cs2"><a href="Vida_Dujmovi%C4%87" title="Vida Dujmović">Dujmović, Vida</a>; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Adjacency Labelling for Planar Graphs (and Beyond)", <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">61st IEEE Annual Symposium on Foundations of Computer Science</a>, pp. 577–588, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2003.04280">2003.04280</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-75520-3_52">10.1007/978-3-540-75520-3_52</a></cite>.

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFRivestVuillemin1975" class="citation cs2"><a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Jean_Vuillemin" title="Jean Vuillemin">Vuillemin, Jean</a> (1975), "A generalization and proof of the Aanderaa-Rosenberg conjecture", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proc. 7th ACM Symposium on Theory of Computing</a>, Albuquerque, New Mexico, United States, pp. 6–11, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.309.7236">10.1.1.309.7236</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800116.803747">10.1145/800116.803747</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16220596">16220596</a></cite><code class="cs1-code">{{citation}}</code>: CS1 maint: location missing publisher (link).

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFKahnSaksSturtevant1983" class="citation cs2">Kahn, Jeff; <a href="Michael_Saks_(mathematician)" title="Michael Saks (mathematician)">Saks, Michael</a>; Sturtevant, Dean (1983), "A topological approach to evasiveness", <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Symposium on Foundations of Computer Science</a>, Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1983.4">10.1109/SFCS.1983.4</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8186-0508-1</bdi></cite>.

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFBenderRon2000" class="citation cs2">Bender, Michael A.; <a href="Dana_Ron" title="Dana Ron">Ron, Dana</a> (2000), "Testing acyclicity of directed graphs in sublinear time", Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., vol. 1853, Berlin: Springer, pp. 809–820, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45022-X_68">10.1007/3-540-45022-X_68</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-67715-4</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1795937">1795937</a></cite>.

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-20" href="https://en.wikipedia.org/wiki/?title=Implicit_graph&oldid=1281486260">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>